import java.util.ArrayList;
import java.util.List;

/**
 * 279. 完全平方数
 * https://leetcode-cn.com/problems/perfect-squares/
 */
public class Solutions_279 {
    public static void main(String[] args) {
        Integer n1 = 12;  // output: 3（4 + 4 + 4）
        Integer n2 = 13;  // output: 2（4 + 9）

        List<Integer> inputs = new ArrayList<>();
        inputs.add(n1);
        inputs.add(n2);

        for (int input : inputs) {
            int result = numSquares(input);
            System.out.println(result);
        }
    }

    /**
     * 解题思路：动态规划
     * 动态转移方程：dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
     */
    public static int numSquares(int n) {
        // dp[12] = 3：和为 n 的完全平方数的最少数量为 3
        int[] dp = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            dp[i] = i;
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}
